A content addressable memory (CAM) is a storage device in which storage locations can be identified by both their location and address through a read operation, as well as by data contents through a search operation. An access by content starts by presenting a search argument to the CAM, wherein a location that matches the argument asserts a corresponding match line. One use for such a memory is in dynamically translating logical addresses to physical addresses in a virtual memory system. In this case, the logical address is the search argument and the physical address is produced as a result of the dynamic match line selecting the physical address from a storage location in a random access memory (RAM). Accordingly, exemplary CAM search operations are used in applications such as address-lookup in network ICs, translation lookaside buffers (TLB) in processor caches, pattern recognition, data compression, etc. CAMs are also frequently used for address-look-up and translation in Internet routers and switches.
A CAM typically includes an array of CAM cells arranged in rows and columns, where each row of the CAM array corresponds to a stored word. The CAM cells in a given row couple to a word line and a match line associated with the row. The word line connects to a control circuit that can either select the row for a read/write operation or bias the word line for a search. The match line carries a signal that, during a search, indicates whether the word stored in the row matches an applied input search word. Each column of the conventional CAM array corresponds to the same bit position in all of the CAM words, while the CAM cells in a particular column are coupled to a pair of bit lines and a pair of search-lines associated with the column. A search data is applied to each pair of search lines, which have a pair of complementary binary signals or unique ternary signals thereon that represent a bit of an input value. Each CAM cell changes the voltage on the associated match line if the CAM cell stores a bit that does not match the bit represented on the attached search lines. If the voltage on a match line remains unchanged during a search, the word stored in that row of CAM cells matches the input word.
Conventional CAM cells can include binary CAM cells as well as ternary CAM (TCAM) cells. A conventional TCAM cell can store three states, including a logic “0”, logic “1” and a “don't care”. When such a TCAM cell stores a logic “0” or logic “1”, the TCAM cell can provide the same essential match operation as a binary CAM cell. However, when such a TCAM cell stores a “don't care” value, the TCAM cell can provide a match result regardless of the compare data value applied to the TCAM cell.
A TCAM can be XY TCAM or a single-cycle update TCAM (also called a value TCAM). In an XY TCAM, each TCAM cell includes an X cell (e.g., 6T SRAM X cell) and a Y cell (e.g., a 6T SRAM Y cell) that share a pair of bit lines. The bit lines are the wires that carry data that is written to or read from either the X cell or the Y cell. Since the X cell and the Y cell share common bit lines, the XY TCAM uses two cycles to update a stored entry in the TCAM cell, i.e., a first cycle to write to the X cell and a second cycle to write to the Y cell. In a value TCAM, the X cell and the Y cell are each connected to their own respective bit lines. In this regard, the value TCAM can perform single cycle updates by writing to both the X cell and the Y cell in a single cycle; however, the additional bit lines add a large amount of space to the circuit. Hence, an XY TCAM provides space savings but uses a two-cycle update operation, whereas a value TCAM provides a single cycle update operation but uses more chip space.